#include<string>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
    int longestSubstring(const string& s, int l, int r, int k) {
        if (l >= r) return 0;
        vector<int>nums(26, 0);
        for (int i = l; i < r; ++i)
            nums[s[i] - 'a']++;
        vector<int>splits;
        for (int i = l; i < r; ++i) {
            if (nums[s[i] - 'a'] < k)
                splits.push_back(i);
        }
        if (splits.size() == 0)
            return r - l;
        splits.push_back(r);
        int ans = 0;
        int prev = l;
        for (int i = 0; i < splits.size(); ++i) {
            ans = max(ans, longestSubstring(s, prev, splits[i], k));
            prev = splits[i] + 1;
        }
        return ans;
    }

public:
    int longestSubstring(string s, int k) {
        return longestSubstring(s, 0, s.length(), k);
    }
};